\begin{proof}[\textbf{Solution~\ref{ex:cryptanalysis:compute_coincidence_index}}]
The coincidence index for each of the ciphertext samples is given in the 
table below.
$$
\begin{array}{rl}
 1. & 0.0438722554890219\\
 2. & 0.0657023320387985\\
 3. & 0.0447239692522711\\
 4. & 0.0629545310820211\\
 5. & 0.0412801243845555\\
 6. & 0.0655225068362645\\
 7. & 0.0412339115637173\\
 8. & 0.0674918061066068\\
 9. & 0.0685573482676622\\
10. & 0.0657341758094024\\
11. & 0.0665847779993272
\end{array}
$$
All but ciphertexts 1, 3, 5 and 7 are consistent with output from 
a simple substitution or transposition cipher.  It is likely that 
the exceptional ones employ a polyalphabetic cipher.  In order to 
distinguish substitution and transposition ciphers, it is necessary 
to look at character distributions, e.g. a close match with the 
frequency distribution of English (or a modern language) suggests 
a transposition cipher.
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:cryptanalysis:identify_periods}}]
Using the average coincidence index of the ciphertext decimations, we 
find that the periods of the ciphertexts 1, 3, 5, and 7 are 11, 6, 14, 
and 9, respectively.  The code to verify this is: 
%\input{code/solution03.1.m}
\input{code/solution03.1.sage}

with output:
%\input{code/solution03.2.m}
\input{code/solution03.2.sage}

Noting the minor peak at $m = 7$, we continue with the loop:
%\input{code/solution03.3.m}
\input{code/solution03.3.sage}
to find the true period is $m = 14$:
%\input{code/solution03.4.m}
\input{code/solution03.4.sage}
Note that the coincidence index for each even test period is slightly
higher, since these involve an averaging over only 7, rather than 14, 
distinct substitutions.
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:cryptanalysis:consider_frequency_distribution}}]
The first step in recovering the keys and plaintext is to determine 
the type of cipher; further techniques are studied in later tutorials.
Note that the ciphertexts 1, 3, 5, and 7 are the result of Vigen\`ere 
cryptosystems, and can be deciphered by statistical analysis of the 
each of the decimations with respect to their periods.
A javascript program from the course web page can be used for this 
purpose.
\end{proof}

%\course{ICE-EM/AMSI Summer School {\it Cryptography}}
%\heading{Summer}{Code Breaking II}{2007}

\begin{proof}[\textbf{Solution~\ref{ex:cryptanalysis:correlation_sequence_translations}}]
Given two strings $S_1 = {\tt pt}$ and $S_2 = {\tt ct}$ with this computes 
their frequency distributions, $\rX_1$ and $\rX_2$ (as discrete probability 
spaces). At each iteration of the {\tt for} loop, an affine translation 
cipher (a cyclic shift by $k$ characters) is constructed.
Then for such cipher $e$, the correlation of $\rX_1$ with $\rX_2\circ e$ is 
constructed.  By comparing a standard plaintext {\tt pt} against affine 
translations of decimations of ciphertext {\tt ct} we are able to break the 
Vigen\`ere enciphering in the exercise below.
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:cryptanalysis:break_Vigenere_ciphers}}]
We have already surmised that the first sample ciphertext, {\tt cipher01.txt}, 
is output from a Vigen\'ere cipher of period 11.  We the definitions as below:
\input{code/solution05.0.sage}
the output of the above code gives
\input{code/solution05.1.sage}
A translation by 7 corresponds to the character \tH, by 0 to \tA, by 18 
to \tS, and by 3 and 4 to \tD and \tE, respectively.  This gives the 
partial enciphering key {\tt *HA**SDEA*E}.  Deciphering with respect to this 
key gives the plaintext blocks {\tt *HE**OETI*I}, {\tt *KT**NPOM*N}, etc.

Relaxing the bound from $r = 0.75$ to $0.50$, one finds multiple solutions
among them the correct solution {\tt SHAKESPEARE}, giving the plaintext
\begin{center}  
{\tt WHENMOSTIWINKTHENDOMINEEYESBESTSEEFORALLTHEDAYTHEYVIEWTHINGSUNRESP}
\end{center}
Why is this a bad key choice?
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:cryptanalysis:break_substitution_ciphers}}]
These maps can be applied to the solution of substitution ciphers by 
finding nearest elements to a known standard for the English language.
For instance, assume that the ciphertext image $x$ of \tE\ has been 
identified, one can look for pairs $xy$ which are the image of the 
plaintext pair \tE\tR, by searching for a nearest vector to:
$$
(0.05674, 0.13071, 0.11352).
$$
This will determine the ciphertext image $y$ of \tR.  This bootstrapping 
procedure successively determines the substitution from the digraph 
frequencies of the ciphertext.
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:cryptanalysis:break_transposition_ciphers}}]
If $i$ and $j$ are the ciphertext images of adjacent positions 
$k$, $k+1$, in each block of length $m$, then the sequence 
$$
c_ic_j,\ c_{i+m}c_{j+m},\ c_{i+2m}c_{j+2m}, \dots 
$$
will have the coincidence index and coincidence discriminant of the 
plaintext.  Note that the measures are invariant under a substitution,
so can be used to break a combination substitution-transposition 
cipher, by first breaking the transposition.  The result will be a 
sequence $i_1, i_2,\dots, i_m$ of indices of positions which ``want''
to be associated.

Note that the measures, coicidence index and coincidence discriminant,
will also be the same for the sequence
$$
c_jc_i,\ c_{j+m}c_{i+m},\ c_{j+2m}c_{i+2m}, \dots 
$$
so we do not directly distinguish the correct order from its reverse,
$i_m, \dots, i_2, i_1$.  This one bit of information can be determined 
at the end, with the savings of being able to assume $i < j$ in testing 
for statistically associated pairs $\{i,j\}$.

Note also that for the incorrect period $m$ there will be little or 
no tendency for statistical association of characters, so by first 
varying the triples $(i,j,m)$, with fixed $i = 1$ and $1 < j \le m$, 
we can determine the probable period $m$ and then recover the entire 
sequence $i_1, i_2, \dots i_m$ by letting $i$ vary. 
\end{proof}

%% \begin{proof}[\textbf{Solution~\ref{ex:cryptanalysis:break_3_time_pads}}]
%% Using the above function, the following lines of input:
%% %\input{code/solution06.1.m}
%% \input{code/solution06.1.sage}
%% generates the output:
%% %\input{code/solution06.2.m}
%% \input{code/solution06.2.sage}

%% By varying the value of {\tt eps} (epsilon), we piece together 
%% likely matching strings for the original plaintexts.

%% \begin{center}
%% \begin{tabular}{cccccccccccccc} \hline
%% $PT_1:$&\tT&\tO&\tB&\tE&\tO&\tR&\xx&\xx&\xx&\xx&\xx&\xx&\xx\\
%% $PT_2:$&\tT&\tH&\tE&\tC&\tA&\tT&\xx&\xx&\xx&\xx&\xx&\xx&\xx\\
%% $PT_3:$&\tW&\tH&\tE&\tN&\tI&\tN&\xx&\xx&\xx&\xx&\xx&\xx&\xx\\ \hline
%% $PT_1:$&\xx&\xx&\xx&\xx&\xx&\tL&\tY&\tI&\tT&\tT&\tO&\xx&\xx\\
%% $PT_2:$&\xx&\xx&\xx&\xx&\xx&\tN&\tT&\tH&\tT&\tH&\tE&\xx&\xx\\
%% $PT_3:$&\xx&\xx&\xx&\xx&\xx&\tH&\tE&\tB&\tE&\tC&\tO&\xx&\xx\\\hline
%% $PT_1:$&\xx&\xx&\xx&\xx&\xx&\xx&\tN&\tO&\tT&\tT&\tO&\xx&\xx\\
%% $PT_2:$&\xx&\xx&\xx&\xx&\xx&\xx&\tI&\tN&\tT&\tH&\tE&\xx&\xx\\
%% $PT_3:$&\xx&\xx&\xx&\xx&\xx&\xx&\tT&\tH&\tE&\tC&\tO&\xx&\xx\\\hline
%% \end{tabular}
%% \end{center}

%% We conjecture that the correct plaintexts are {\tt TOBEORNOTTO**}, 
%% {\tt THECATINTHE**}, and {\tt WHENINTHECO**}, leaving the final
%% characters to pure guesswork.
%% \end{proof}
